package 题目集.dfs;

import java.util.Scanner;

/**
 * todo
 * https://www.acwing.com/problem/content/167/
 */
public class 小猫爬山 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        long maxValue = Long.MAX_VALUE;
        long sqrt = (long) Math.sqrt(maxValue);
    }

    /**
     * 已经放入u只小猫，且花费了k个车的最小值
     */
    public static void dfs(int u, int k) {
        if(k>=ans) return;
        if(u==n) {
            ans = k;
            return;
        }
        for (int i = 0; i <=k; i++) {
            if (cat[u]<= car[i]) {   //如果第i个车还能放下第u只小猫
                car[i]-= cat[u];
                dfs(u+1,k);
                car[i]+= cat[u];
            }
        }
        car[k+1]-= cat[u];  //新开一辆车
        dfs(u+1,k+1);
        car[k+1]+= cat[u];
    }
    static int n;
    static int[] cat;
    static int[] car;
    static int ans = Integer.MAX_VALUE;
}
